/*
 * @lc app=leetcode.cn id=350 lang=csharp
 *
 * [350] 两个数组的交集 II
 */

// @lc code=start
public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        var dict1 = new Dictionary<int, int>();
        var dict2 = new Dictionary<int, int>();
    
        for(int i = 0; i < nums1.Length; ++i)
        {
            int num = nums1[i];
            if(!dict1.TryGetValue(nums1[i], out int v))
            {
                dict1[num] = 1;
            }
            else
            {
                dict1[num] = v + 1;
            }
        }
        for(int i = 0; i < nums2.Length; ++i)
        {
            int num = nums2[i];
            if(!dict2.TryGetValue(nums2[i], out int v))
            {
                dict2[num] = 1;
            }
            else
            {
                dict2[num] = v + 1;
            }
        }
        
        var count = 0;
        foreach (var key in dict1.Keys)
        {
            if(!dict2.ContainsKey(key))
            {
                dict1.Remove(key);
            }
            else
            {
                int v = Math.Min(dict1[key], dict2[key]);
                count += v;
                dict1[key] = v; 
            }
        }
        
        var ans = new int[count];
        int ix = -1;
        foreach (var key in dict1.Keys)
        {
            for (int i = 0; i < dict1[key]; ++i)
            {
                ans[++ix] = key;
            }
        }
        return ans;
    }
}
// @lc code=end

